﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;


//最⻓回⽂⼦串（回⽂串）
//https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af?tpId=182&tqId=34752&ru=/exam/oj

//class Solution {
//public:
//    int getLongestPalindrome(string s) {
//        int ret = 1, sz = s.size();
//        for (int i = 0; i < sz; i++)
//        {
//            int left = i - 1, right = i + 1;
//            while (left >= 0 && right < sz && s[left] == s[right])
//            {
//                left--;
//                right++;
//            }
//            ret = max(ret, right - left - 1);
//
//            left = i, right = i + 1;
//            while (left >= 0 && right < sz && s[left] == s[right])
//            {
//                left--;
//                right++;
//            }
//            ret = max(ret, right - left - 1);
//        }
//        return ret;
//    }
//};


//2. 买卖股票的最好时机(⼀)（贪⼼）
//https://www.nowcoder.com/practice/351b87e53d0d44928f4de9b6217d36bb?tpId=230&tqId=39767&ru=/exam/oj

//int main()
//{
//	int n;
//	int arr[100005];
//	cin >> n;
//	for (int i = 0; i < n; i++)
//	{
//		cin >> arr[i];
//	}
//	
//	int in = arr[0], ret = 0;
//	for (int i = 1; i < n; i++)
//	{
//		int out = arr[i];
//		in = min(in, arr[i - 1]);
//		ret = max(ret, out - in);
//	}
//	cout << ret; 
//}

//过河卒（动态规划 - 路径问题）
//https://www.nowcoder.com/practice/cc1a9bc523a24716a117b438a1dc5706?tpId=230&tqId=40428&ru=/exam/oj


//int board[25][25] = { 0 };
//int vis[25][25] = { 1,0 };
//int dx[2] = { 0,1 };
//int dy[2] = { 1,0 };
//int m, n, a, b, ret = 0;
//
//void dfs(int x, int y)
//{
//    if (x == m && y == n)
//    {
//        ret++;
//        return;
//    }
//
//    for (int i = 0; i < 2; i++)
//    {
//        int nx = x + dx[i], ny = y + dy[i];
//        if (nx >= 0 && nx <= m && ny >= 0 && ny <= n &&
//            vis[nx][ny] == 0 && board[nx][ny] == 0)
//        {
//            vis[nx][ny] = 1;
//            dfs(nx, ny);
//            vis[nx][ny] = 0;
//        }
//    }
//    return;
//}
//
//int main()
//{
//    cin >> m >> n >> a >> b;
//    board[a][b] = 1;
//    for (int i = 0; i <= m; i++)
//    {
//        for (int j = 0; j <= n; j++)
//        {
//            if (abs(i - a) + abs(j - b) == 3 && i != a && j != b)
//            {
//                board[i][j] = 1;
//            }
//        }
//    }
//    if (board[0][0] == 1)
//    {
//        cout << 1 << endl;
//        return 0;
//    }
//
//    dfs(0, 0);
//    cout << ret << endl;
//    
//    return 0;
//}

//过河卒（动态规划 - 路径问题）
//https://www.nowcoder.com/practice/cc1a9bc523a24716a117b438a1dc5706?tpId=230&tqId=40428&ru=/exam/oj

//int n, m, x, y;
//long long dp[25][25];
//
//int main()
//{
//    cin >> m >> n >> x >> y;
//    x += 1, y += 1;
//    dp[1][0] = 1;
//    for (int i = 1; i <= m + 1; i++)
//    {
//        for (int j = 1; j <= n + 1; j++)
//        {
//            if ((abs(i - x) + abs(j - y) == 3 && i != x && j != y)
//                || (i == x && j == y))
//            {
//                dp[i][j] = 0;
//            }
//            else
//            {
//                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
//            }
//        }
//    }
//
//    cout << dp[m + 1][n + 1] << endl;
//
//    return 0;
//}